package com.example.demo.tree;


class Node {
    int data;
    Node left, right, parent;
    int color;

    Node(int data) {
        this.data = data;
        left = right = parent = null;
        color = 1;
    }
}
public class RedBlackTree {
    private Node root;

    private void left_rotate(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    private void right_rotate(Node x) {
        Node y = x.left;
        x.left = y.right;
        if (y.right != null) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        y.right = x;
        x.parent = y;
    }

    void fix_insert(Node k) {
        Node u;
        while (k.parent.color == 1) {
            if (k.parent == k.parent.parent.right) {
                u = k.parent.parent.left;
                if (u.color == 1) {
                    u.color = 0;
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.left) {
                        k = k.parent;
                        right_rotate(k);
                    }
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    left_rotate(k.parent.parent);
                }
            } else {
                u = k.parent.parent.right;

                if (u.color == 1) {
                    u.color = 0;
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.right) {
                        k = k.parent;
                        left_rotate(k);
                    }
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    right_rotate(k.parent.parent);
                }
            }
        }
        k.parent.parent.color = 0;
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);

        n1.left = n2;
        n2.left = n3;
        n3.left = n4;
        n4.left = n5;
        n5.left = n1;
        n2.parent = n1;
        n3.parent = n1;
        n4.parent = n1;
        n5.parent = n1;
        RedBlackTree redBlackTree = new RedBlackTree();
        redBlackTree.fix_insert(n1);
        redBlackTree.fix_insert(n2);
        redBlackTree.fix_insert(n3);
        redBlackTree.fix_insert(n4);
        redBlackTree.fix_insert(n5);
        redBlackTree.fix_insert(n6);
    }
}
